// 版权所有2011 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ast

import (
	"go/token"
	"sort"
	"strconv"
)

// SortImports对f中导入块中连续导入行的运行进行排序。
// 如果可以在不丢失数据的情况下删除重复导入，它还会删除重复导入。
func SortImports(fset *token.FileSet, f *File) {
	for _, d := range f.Decls {
		d, ok := d.(*GenDecl)
		if !ok || d.Tok != token.IMPORT {
			// 不是进口报关单，所以我们结束了。
			// 进口总是第一位的。
			break
		}

		if !d.Lparen.IsValid() {
			// 不是块：默认排序。
			continue
		}

		// 识别并排序连续行上的规格运行。
		i := 0
		specs := d.Specs[:0]
		for j, s := range d.Specs {
			if j > i && lineAt(fset, s.Pos()) > 1+lineAt(fset, d.Specs[j-1].End()) {
				// j开始新的跑步。结束这一次。
				specs = append(specs, sortSpecs(fset, f, d.Specs[i:j])...)
				i = j
			}
		}
		specs = append(specs, sortSpecs(fset, f, d.Specs[i:])...)
		d.Specs = specs

		// 重复数据消除可以在rparen前留下一个空行；把它清理干净。
		if len(d.Specs) > 0 {
			lastSpec := d.Specs[len(d.Specs)-1]
			lastLine := lineAt(fset, lastSpec.Pos())
			rParenLine := lineAt(fset, d.Rparen)
			for rParenLine > lastLine+1 {
				rParenLine--
				fset.File(d.Rparen).MergeLine(rParenLine)
			}
		}
	}
}

func lineAt(fset *token.FileSet, pos token.Pos) int {
	return fset.PositionFor(pos, false).Line
}

func importPath(s Spec) string {
	t, err := strconv.Unquote(s.(*ImportSpec).Path.Value)
	if err == nil {
		return t
	}
	return ""
}

func importName(s Spec) string {
	n := s.(*ImportSpec).Name
	if n == nil {
		return ""
	}
	return n.Name
}

func importComment(s Spec) string {
	c := s.(*ImportSpec).Comment
	if c == nil {
		return ""
	}
	return c.Text()
}

// 崩溃表示是否可以删除prev，只留下next。
func collapse(prev, next Spec) bool {
	if importPath(next) != importPath(prev) || importName(next) != importName(prev) {
		return false
	}
	return prev.(*ImportSpec).Comment == nil
}

type posSpan struct {
	Start token.Pos
	End   token.Pos
}

type cgPos struct {
	left bool // 如果注释位于规范左侧，则为true，否则为false。
	cg   *CommentGroup
}

func sortSpecs(fset *token.FileSet, f *File, specs []Spec) []Spec {
	// 即使规格已经排序，也不能在此短路，因为它们可能还需要重复数据消除。
	// 然而，一个单独的导入可能会被安全地忽略。
	if len(specs) <= 1 {
		return specs
	}

	// 记录规格的位置。
	pos := make([]posSpan, len(specs))
	for i, s := range specs {
		pos[i] = posSpan{s.Pos(), s.End()}
	}

	// 识别此范围内的注释。
	begSpecs := pos[0].Start
	endSpecs := pos[len(pos)-1].End
	beg := fset.File(begSpecs).LineStart(lineAt(fset, begSpecs))
	endLine := lineAt(fset, endSpecs)
	endFile := fset.File(endSpecs)
	var end token.Pos
	if endLine == endFile.LineCount() {
		end = endSpecs
	} else {
		end = endFile.LineStart(endLine + 1) // 下一行的开头
	}
	first := len(f.Comments)
	last := -1
	for i, g := range f.Comments {
		if g.End() >= end {
			break
		}
		// g.End（）<End 
		if beg <= g.Pos() {
			// 注释在[beg，End]范围内[of import declarations 
			if i < first {
				first = i
			}
			if i > last {
				last = i
			}
		}
	}

	var comments []*CommentGroup
	if last >= 0 {
		comments = f.Comments[first : last+1]
	}

	// 将每个注释分配给同一行上的导入规范。
	importComments := map[*ImportSpec][]cgPos{}
	specIndex := 0
	for _, g := range comments {
		for specIndex+1 < len(specs) && pos[specIndex+1].Start <= g.Pos() {
			specIndex++
		}
		var left bool
		// 块注释可以出现在第一个导入规范之前。
		if specIndex == 0 && pos[specIndex].Start > g.Pos() {
			left = true
		} else if specIndex+1 < len(specs) && // 也可以出现在导入规范的左侧。
			lineAt(fset, pos[specIndex].Start)+1 == lineAt(fset, g.Pos()) {
			specIndex++
			left = true
		}
		s := specs[specIndex].(*ImportSpec)
		importComments[s] = append(importComments[s], cgPos{left: left, cg: g})
	}

	// 按导入路径对导入规范进行排序。
	// 尽可能在不丢失数据的情况下删除重复项。
	// 重新分配导入路径，使其具有相同的位置序列。
	// 将每个注释重新分配到同一行的规范中。
	// 按新位置对评论进行排序。
	sort.Slice(specs, func(i, j int) bool {
		ipath := importPath(specs[i])
		jpath := importPath(specs[j])
		if ipath != jpath {
			return ipath < jpath
		}
		iname := importName(specs[i])
		jname := importName(specs[j])
		if iname != jname {
			return iname < jname
		}
		return importComment(specs[i]) < importComment(specs[j])
	})

	// 重复数据消除。多亏了我们的分类，我们才可以考虑ABCFDG 
	deduped := specs[:0]
	for i, s := range specs {
		if i == len(specs)-1 || !collapse(s, specs[i+1]) {
			deduped = append(deduped, s)
		} else {
			p := s.Pos()
			fset.File(p).MergeLine(lineAt(fset, p))
		}
	}
	specs = deduped

	// 修复注释位置
	for i, s := range specs {
		s := s.(*ImportSpec)
		if s.Name != nil {
			s.Name.NamePos = pos[i].Start
		}
		s.Path.ValuePos = pos[i].Start
		s.EndPos = pos[i].End
		for _, g := range importComments[s] {
			for _, c := range g.cg.List {
				if g.left {
					c.Slash = pos[i].Start - 1
				} else {
					// 导入规范的右侧可以同时包含块注释和行注释
					// 。在这种情况下，它们都将具有相同的位置
					// 但是在格式化AST时，行注释会在块注释之后移动到
					// 中。
					c.Slash = pos[i].End
				}
			}
		}
	}

	sort.Slice(comments, func(i, j int) bool {
		return comments[i].Pos() < comments[j].Pos()
	})

	return specs
}
